觀前提醒：

1. 我預設大家已經先思考並分析過題目，沒啥想法才開始 google 找解題靈感。若無，建議每題先花 1~2 顆番茄鐘的時間來分析題目比較好。可參考番茄鐘工作法。
2. 承上，既然已經有思考過了，那我這邊直接 po 題目 + 解題想法 + code +心得 。若已經在 code 內有足夠的註解了，那我可能解題想法 & 心得的部分就不會寫太多，免得干擾你的思考。
3. 所有解法都是已經取得系統的 Accepted，但或許不是最優解法，請多包涵。
4. 若對於解法不太懂，可以嘗試用 Chrome 的 debugger 來試跑看看 (教學文)
5. 最後，歡迎在下面留言指教~教學相長才會進步歐~

題目

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version. 

解題想法

大家看完這題後，如果想直接寫個迴圈然後用暴力法一個個慢慢嘗試，保證會直接TLE~
所以要能輕鬆KO這題，唯一解就是只能採用陣列搜尋中，最經典的二元搜尋(binary search)演算法，來處理囉~

CODE

/**
 * Definition for isBadVersion()
 *
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function (isBadVersion) {
  /**
   * @param {integer} n Total versions
   * @return {integer} The first bad version
   */
  return function (n) {
    let left = 1;
    let right = n;
    while (left <= right) {
      let mid = Math.floor((left + right) / 2);
      if (isBadVersion(mid)) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return left;
  };
};

心得

我猜可能大家會問：為何最後是回傳 left? 照著維基百科上的寫法來看，最後應該是要回傳 mid 啊?
小弟先請大家冷靜，以下是 Leetcode 解說的舉例

Scenario #1: isBadVersion(mid) => false

 1 2 3 4 5 6 7 8 9
 G G G G G G B B B       G = Good, B = Bad
 |       |       |
left    mid    right

Scenario #2: isBadVersion(mid) => true

 1 2 3 4 5 6 7 8 9
 G G G B B B B B B       G = Good, B = Bad
 |       |       |
left    mid    right

我們從以上兩個舉例，可以觀察到：Scenario #1 &　Scenario #2 的左側皆為 good ，所以依照 binary search 的概念，當左側指針第一次不為 good 時，就代表此為 first bad version。

可參考以下的圖示，方便了解此code的運作過程
(手繪真D悲劇，抱歉~)

因為人家測資的排序，都是先 G 再 B ，所以我們只要回傳最新的 left 指針位置，那就代表該版本為 the First Bad Version

謝謝大家的收看，LeetCode 小學堂我們下次見~